1. Field of the Invention
The present invention relates generally to sequential decoding, and more specifically to techniques for sequentially decoding an incoming (received) data sequence in an attempt to find the most likely path in a code tree.
2. Description of Related Art
Prior to turning to the present invention, it is deemed preferable to describe, with reference to FIGS. 1-5, sequential decoding technology known as the Fano algorithm.
Reference is made to FIG. 1, a simple example of an encoder 10, which takes the form of a binary convolutional encoder, is illustrated in block diagram form. The encoder 10 is comprised of a shift-register consisting of three flip-flops 12a-12c and two exclusive-or gates 14a-14b, all of which are coupled as shown. In order to initialize the flip-flops 12a-12c, a control signal, which takes a logic level 0 (for example), is applied to the flip-flops 12a-12c by way of an input terminal 16c. Each of the flop-flops 12a-12c, in response to logic level 0 of the control signal, is cleared to zero. After the initialization of the flip-flops 12a-12c, the control signal continues to assume a logic level 1. When a plurality of information symbols are successively applied to the flip-flop 12a via an input terminal 16b while the control signal takes a logic level 1, they are shifted one by one to the subsequent flop-flops 12b and 12c in synchronism with a clock signal applied to the flip-flops 12a-12c by way of an input terminal 16a. In the above, each of the information symbols applied to the encoder 10 via the input terminal 16b is binary, and therefore, to be precise, has to be referred to as an information bit. However, in the instant disclosure, for the sake of convenience of description, the information bit may typically be referred to as information symbol.
The exclusive-or gate 14a has four inputs respectively coupled to receive directly the information symbol by way of the input terminal 16b and the outputs of the flip-flops 12a-12c, and then applies the output thereof to an output terminal 18b. The other exclusive-or gate 14b has three inputs for respectively directly receiving the information symbols via the input terminal 16b and the outputs flip-flops 12b and 12c, and applies the output thereof to an output terminal 18c. On the other hand, the incoming information symbol is directly fed to an output terminal 18a. 
Assuming that information symbols u1, u2, u3, . . . are sequentially applied to the encoder 10 through the input terminal 16b. The initial information symbol u1 determines first three encoded data sequence x1(1), x1(2), x1(3) (=x1) which appear at the output terminals 18a-18c. The next three encoded data sequence x2(1)), x2(2)), x2(3)(=x2) are functions of the first two information symbols u1 and u2, and the following three encoded symbols x3(1)), x3(2)), x3(3))(=x3) are functions of u1, u2, u3, and so forth. This dependence of the encoded data sequence upon the inputted information symbol sequence imposes a treelike structure on the set of the encoded data sequences, which is illustrated in FIG. 2.
Referring to FIG. 2, the leftmost node of code tree, indicated by a black circle, is called an origin node, while the rightmost nodes of the code tree are respectively called terminal nodes. The leftmost symbol triplets 111 and 000 along the upper and lower branches stemming from the origin node, correspond to the responses of the encoder 10 to the initial information symbol (viz., u1) 1 or 0. Branching off to the right from the response 111 to an initial 1 are the responses to a 1 or 0 following an initial 1, and so forth. By way of example, the response of the encoder 10 to the information sequence u1=1, u2=1, u3=0, u4=0 is highlighted in the tree code of FIG. 2.
As mentioned above, the encoder 10 forms a path through the code tree corresponding to an incoming information symbol sequence to be encoded. It follows that sequential decoding can be regarded as the process of determining the path in the code tree which was followed by the encoder. That is to say, a sequential decoder reconstructs the encoder""s path through the tree on the basis of the received data sequence.
FIG. 3 is a diagram showing a code tree for use in sequentially decoding a received data sequence. Although the code tree of FIG. 3 is exactly identical to that shown in FIG. 2 (viz., replica of code tree of FIG. 2), it is reiterated for the sake of convenience of description.
Assuming that the encoder 10 of FIG. 1 outputs a data sequence 111 101 001 000 which is transmitted to a receiver via a binary symmetrical communication channel, and the received data sequence is 101 101 001 000 due to deterioration during the transmission over a noisy channel. In this case, the second bit of the first block is erroneously received.
As mentioned above, the first three symbols (bits) of the received data sequence should be either 111 or 000, and in this particular case, it is hypothesized that the first three symbols transmitted are 111 in that the Hamming distance is shorter than the other triplet 000. If this assumption is correct, it is hypothesized that the next three symbols are 101, and in a similar manner, it is further hypothesized that the following symbols are 001 000. That is, it is hypothesized that the data sequence 111 101 001 000 has been transmitted as highlighted in a bold line in FIG. 3. The sequential hypothesizing as mentioned above is able to reduce the number of data sets (i.e., 111, 001, . . . along each branch) to be searched only two at each of the hypothesizing operations in this case.
As in the above case, assuming that the data sequence 111 101 001 000 has been transmitted. However, in this instance, it is assumed that due to more noisy channel circumstances, the received data sequence is contaminated as 010 101 001 000. In such a case, it is hypothesized that the first three symbols are 000 due to the shorter Hamming distance. Since this hypothesis is correct, it follows that the following code symbols are hypothesized as 111 101 001. Thus, the data sequence received is hypothesized as 000 111 101 001 as indicated by a phantom line in FIG. 3. In this case, however, 4 symbol (bits) are erroneously presumed. This implies that once an erroneous hypothesis is made, the subsequently decoded symbols tend to be rendered uncorrelative or irrelevant with the received data sequence.
Throughout the instant disclosure, a term xe2x80x9cpathxe2x80x9d implies a trail or passage from the origin node to a certain point (node) in the tree, or the most likely path up to a certain terminal node in the tree (viz., solution of the decoder). Further, a partial sequence xj denotes a path at j-th level in the code tree as shown in FIG. 3. As will be understood, the number of paths at the level 1 (viz., x1) is two, and that at the level 2 (viz., x2) is four, and so on. However, the partial sequences at the same level will not be discriminated with one another in the following descriptions.
In FIG. 3, a plurality of nodes in the code tree are denoted by n0, n1(1), n1(2), n2(1), . . . , n4(15), and n4(16), while a plurality of branches in the tree are denoted by b1(1), b1(2), . . . , b4(15), and b4(16).
The decoder is configured such as to notice that if the decoded data symbols are found to deviate from those of the received data sequence in excess of a predetermined threshold, the previous hypothesis has been erroneous. More specifically, if the decoder notices that the earlier hypothesis is erroneous at a given preceding node, the decoder returns to this node, changing the suspected branch (or node), and proceeds along a new branch or path in the tree. Each of these successive hypotheses is able to reduce the number of selections to be checked, simplifying the succeeding hypothesizing operations, and being able to give the information via which the correctness of earlier hypothesis can be determined.
FIGS. 4A-4C are diagrams schematically illustrating a set of rules according to the sequential decoding algorithm, which rules consists of three kinds of moves: forward, lateral, and backward of the decoder (or the moves of a pointer). On the forward move (FIG. 4A), the decoder advances the pointer along one branch b2(1) to the right in the code tree from the previously hypothesized node. The lateral move (FIG. 4B) is a move from one node b2(1) to another b2(2). In more specific term, on the lateral move, the pointer moves backward to the node from which the branch b2(1) stems, after which the pointer advances along the node b2(2). The backward move (FIG. 4(c)) is that the decoder retreats the pointer along one branch b2(1) to the previously examined branch b1(1) in the code tree.
The principle of the Fano algorithm is described in a paper entitled xe2x80x9cA Heuristic Discussion of Probabilistic Decodingxe2x80x9d by Robert M. Fano, IEEE Transactions of Information Theory, Vol. IT-9, p. 64-74, April 1963, or a book entitled xe2x80x9cInformation Theory and Reliable Communicationxe2x80x9d by Robert G. Gallager, John Wiley and Sons, Inc., 1968.
As to the history of the sequential decoding, reference should be made, for example, to a paper entitled xe2x80x9cBacktrack Programmingxe2x80x9d by Solomon W. Golomb and Leonard D. Baumert, Journal of the Association for Computing Machinery, Vol. 12, No. 4, pp. 516-524, October 1965.
Prior to implementing the sequential decoding, the decoder previously stores the code tree which is a replica of that in an encoder and has been exemplified in FIG. 3. The code tree stored in the decoder typically takes the form of a look-up table which includes a plurality of branches (or nodes) with the logical relationship therebetween. That is to say, the branches (or nodes) can be specified using memory addresses each of which may be referred to as the pointer in the instant disclosure.
As mentioned above, the Fano algorithm is to decode the inputted data sequence, which can be represented in a tree structure, by discarding an improbable path (node or branch) and search new one through the code tree.
The Fano algorithm however is in fact more complicate. FIG. 5 is a table showing the operation rules of the conventional Fano algorithm, which table is given in the aforesaid book by Galleger. In FIG. 5, T denotes a threshold, and xcex93 denotes a path metric called the Fano metric and is given by
xcex93(xi)=xe2x88x92log{p(y)/p(y|xj)}xe2x88x92B(xjxe2x88x921)xe2x80x83xe2x80x83(1) 
where p(y) is a probability of occurrence of an inputted data sequence y in the tree, p(y|xj) is a probability of occurrence of the data sequence y under the condition that a path xj of length (or depth) j in the tree occurs, and p(xj) is a probability of occurrence of the path xj of length j in the tree. Further, B(xjxe2x88x921) of equation (1) represents a bias in connection with the path xjxe2x88x921 in the tree, and is selected such that if xj is a path forming part of the maximum likelihood (most likely) path, the expected value of xcex93(xj) becomes positive, and otherwise, the expected value of xcex93(xj) becomes negative.
Further, in FIG. 5, the character xe2x80x9cIxe2x80x9d denotes increment of the threshold T. More specifically, xe2x80x9cIxe2x80x9d implies that the threshold T is incremented by txcex94 (viz., T=T+txcex94) where t is the maximum integer satisfying xcex93(xj)xe2x88x92xcex94 less than T+txcex94xe2x89xa6xcex93(xj). Still further, the character xe2x80x9cNxe2x80x9d represents no change of the threshold T, and xe2x80x9cDxe2x80x9d the decrement of the threshold T (viz. T=Txe2x88x92xcex94). Still further, in FIG. 5, xe2x80x9cFxe2x80x9d denotes a forward move of the pointer so as to examine a subsequent branch or node in the code tree, xe2x80x9cLxe2x80x9d a lateral move of the pointer, and xe2x80x9cBxe2x80x9d a backward move of the pointer.
As is well known in the art, according to the Fano algorithm, the decoder will move forward through the code tree as long as the metric value along a path being examined continues to increase. When the metric value falls below a threshold, the decoder retreats and starts to examine other path leaving the same node. If no path stemming from the same node can be found whose path metric exceeds the threshold, the threshold is decreased and the decoder attempts to move forward again with a decreased threshold. No node (or branch) is ever examined twice with the same threshold, and accordingly, the decoder is not trapped in a loop.
It is understood, from the just-mentioned brief descriptions of the Fano algorithm, that this algorithm is able to markedly improve the process time compared to unconditionally checking all nodes (or branches). Therefore, the Fano algorithm has found extensive application in the filed of error control decoding. As an example of a practical use of the Fano algorithm, reference should be made to U.S. Pat. No. 3,665,396.
It is known in the art that if a code rate R is smaller than a computational cutoff rate Rcomp, the average time of computation, needed to search the most likely path through the code tree in the Fano algorithm, is proportional to the length N(x) of the most likely path. The code rate R is a ratio of the number of bits needed to represent one symbol of information sequence (viz., input to an encoder) to the number of bits needed to represent one symbol of data sequence (viz., output of the encoder). On the other hand, the computational cutoff rate Rcomp is determined depending on the above-mentioned probabilities p(y), p(y|xj) and p(xj) and is a little bit smaller than an entropy H of the information symbol sequence.
However, the conventional Fano algorithm has encountered the difficulties that provided that the paths in the code tree do not occur equiprobably, it is often the case that the average time of computation until determining the most likely path in the tree, is not proportional to the length (N(x)) of the most likely path and thus liable to diverge. This is because if the paths in the code tree do not occur equiprobably, the value corresponding to the entropy H of the information symbol sequence becomes smaller, thereby lowering the computational cutoff rate Rcomp. Further, if the value corresponding to the code rate R becomes larger than that corresponding to Rcomp, the average time of computation for searching the most likely path in the tree is no longer proportional to the length N(x) thereof, and thus resulting in the fact that the number of computing processes diverges. In practice, however, since the number of the paths in the code tree is finite, such a problem of divergence may be somewhat rare. Nonetheless, in the case where the paths in the code tree do not occur equiprobably, the amount of computation increases to an extent of practically unacceptable level.
Accordingly, the conventional Fano algorithm has not ever been applied to the technical fields such as pattern recognition, speech recognition, etc. wherein the paths in the code tree occur equiprobably.
It is therefore an object of the present invention to provide a sequential decoding apparatus which is well suited to decode an incoming data sequence in an application such as pattern recognition, speech recognition, etc. wherein the partial sequences in the code tree do not occur equiprobably.
Another object of the present invention is to provide a sequential decoding method which is well suited to decode an incoming data sequence in an application such as pattern recognition, speech recognition, etc. wherein the partial sequences in the code tree do not occur equiprobably.
In brief, these objects are achieved by the techniques wherein in order to sequentially decode a plurality of symbol sets of an incoming data sequence with less amount of computation in an application wherein paths in a code tree do not occur equiprobably, a code tree is previously memorized in a decoder. This code tree comprises a plurality of paths defined by a plurality of sequences of nodes. A pointer generator is provided for generating a pointer that defines a node that specifies a path in the code tree. A plurality of branch metric generators each generates a metric of a branch which forms part of a path and which is to be examined with a corresponding symbol set of the incoming data sequence. Further, a plurality of path metric generators are provided which respectively receive the branch metrics from the plurality of branch metric generators and respectively generate path metrics using the branch metrics. A controller controls the pointer generator and the plurality of path metric generators such as to maximize each of the plurality of path metrics at each of decoding steps for sequentially decoding the symbol sets of the incoming data sequence.
One aspect of the present invention resides in an apparatus for sequentially decoding a plurality of symbol sets of an incoming data sequence. The apparatus comprises a memory for storing a code tree which comprises a plurality of paths defined by a plurality of sequences of nodes. A pointer generator is provided for generating a pointer which defines a node which specifies a path in the code tree. A plurality of branch metric generators are also provided, each of which generates a metric of a branch which forms part of a path and which is to be examined with a corresponding symbol set of the incoming data sequence. A plurality of path metric generators respectively receive the branch metrics from the plurality of branch metric generators and respectively generate path metrics using the branch metrics. A controller controls the pointer generator and the plurality of path metric generators such as to maximize each of the plurality of path metrics at each of decoding steps for sequentially decoding the symbol sets of the incoming data sequence.
Another aspect of the present invention resided in a method sequentially decoding a plurality of symbol sets of an incoming data sequence by way of data search through a code tree stored in a memory. The code tree comprises a plurality of paths defined by a plurality of sequences of nodes. The method includes the steps of: (a) generating a pointer which defines a node which specifies a path in the code tree; (b) generating a plurality of branch metrics each of which relates to a branch which forms part of a path and which is to be examined with a corresponding symbol set of the incoming data sequence; (c) determining a plurality of path metrics using the plurality of branch metrics; and (d) controlling the generation of the pointer and the determination of the plurality of path metrics such as to maximize each of the plurality of path metrics at each of decoding steps for sequentially decoding the symbol sets of the incoming data sequence.